Low density parity-check (LDPC) codes were first proposed by Gallager in 1962, and then “rediscovered” by MacKay in 1996. LDPC codes have been shown to achieve an outstanding performance that is very close to the Shannon transmission limit.
LDPC codes are based on a binary parity-check matrix H with n columns and m=n−k rows that has the following properties:                1. Each row consists of p number of “ones;”        2. Each column consists of γ number of “ones;”        3. The number of “ones” in common between any two columns, denoted as λ, is no greater than one; and        4. Both p and γ are small compared to the length of the code and the number of rows in H.        
For every given binary source message u={u0, . . . , uk-1} of length k, the LDPC encoder builds a binary codeword v={v0, . . . , vn-1} of length n where (n>k), such that Hv=0. The codeword consists of two parts. The first k bits of the codeword are equal to the bits of the source message. The other n−k bits of the codeword are the so-called parity-check bits p={p0, . . . , pn-k-1}. The main task of the encoder is to calculate these parity-check bits p for the given input message u.
To simplify matrix operations, the parity check matrix can be composed of pγcells. The cells are arranged in p columns and γ rows, as given below.
  H  =      (                                        H                          0              ,              0                                                ⋯                                      H                          0              ,                              p                ⁢                                                                  ⁢                …1                                                                          ⋯                          ⋯                          ⋯                                                  H                                          p                ⁢                                                                  ⁢                …1                            ,              0                                                ⋯                                      H                                          γ                ⁢                                                                  ⁢                …1                            ,                              p                ⁢                                                                  ⁢                …1                                                          )  
Each cell is a t×t permutation matrix (n=pt, n−k=γt). It contains exactly one value of “one” in every row and every columns Therefore, properties (1), (2), and (4) as listed above are satisfied by the construction of the matrix.
Matrix H can be considered as a concatenation of two sub matrices: A and B. Matrix A contains k columns and (n−k) rows. It includes the first k columns of H. Matrix B is a square matrix that contains (n−k) columns and (n−k) rows. It includes the last (n−k) columns of matrix H. The source equation Hv=0 can then be rewritten as Au+Bp=0.
The most famous algorithm for decoding LDPC codes is called the iterative message-passing algorithm. Each iteration of this algorithm consists of two stages. In stage 1 (the row operations), the algorithm computes messages for all of the check nodes (the rows). In stage 2 (the column operations), the algorithm computes messages for all of the bit nodes (the columns), and sends them back to the check nodes associated with the given bit nodes. There are many different implementations of this message-passing algorithm, but all of them use two-stage operations. Further, in each of these implementations, the second step starts only after all of the messages for all of the rows have been calculated.
As with all information processing operations, it is desirable for the procedure to operate as quickly as possible, while consuming as few resources as possible. Unfortunately, LDPC codes such as those described above typically require a relatively significant overhead in terms of the time and the memory required for them to operate.
What is needed is an LDPC code that operates in a more efficient manner, such as by reducing the amount of time or the amount of memory that is required by the operation.